package algorithms.question.class01;

/**
 * leetcode 329
 * 给定一个二维数组matrix，
 * 你可以从任何位置出发，走向上下左右四个方向
 * 返回能走出来的最长的递增链长度
 *
 * @author guichang
 * @date 2021/7/29
 */

@SuppressWarnings("all")
public class Code5_最长递增连 {

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int N = matrix.length;
        int M = matrix[0].length;
        // 最长的递增链
        int ans = 0;
        int[][] cache = new int[N][M];
        // 可以选择任意坐标开始
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                ans = Math.max(ans, process(matrix, i, j, cache));
            }
        }
        return ans;
    }

    /**
     * 从任意坐标i、j出发的最长递增链
     */
    private int process(int[][] arr, int i, int j, int[][] cache) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        int up = i - 1 >= 0 && arr[i - 1][j] > arr[i][j] ? process(arr, i - 1, j, cache) : 0;
        int down = i + 1 < arr.length && arr[i + 1][j] > arr[i][j] ? process(arr, i + 1, j, cache) : 0;
        int left = j - 1 >= 0 && arr[i][j - 1] > arr[i][j] ? process(arr, i, j - 1, cache) : 0;
        int right = j + 1 < arr[0].length && arr[i][j + 1] > arr[i][j] ? process(arr, i, j + 1, cache) : 0;
        int res = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
        cache[i][j] = res;
        return res;
    }

}